package Stackdemo;

import demo3.AllCard;

import java.util.Arrays;
import java.util.Stack;

public class Mystack {
    public int[] elem;
    public int size;
    public static final int capacity = 1;

    public Mystack() {
        this.elem = new int[capacity];
    }

    public void push(int x) {
        if (isFull(elem)) {
            this.elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[size++] = x;
    }

    public boolean isFull(int[] elem) {
        return size == elem.length;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int pop() throws EmptyException {
        if (isEmpty()) {
            throw new EmptyException("栈为空！");
        }
        int s1 = elem[size - 1];
        size--;
        return s1;
    }

    public int peak() throws EmptyException {
        if (isEmpty()) {
            throw new EmptyException("栈为空！");
        }
        return elem[size - 1];
    }

    // 栈的压入、弹出序列
    public boolean IsPopOrder(int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < popV.length; i++) {
            stack.push(pushV[i]);
            while (!stack.isEmpty() && j < popV.length && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

    // 利用栈来判断括号是否匹配
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i);
            if (a == '[' || a == '{' || a == '(') {
                stack.push(a);
            } else {
                if (stack.empty()) {
                    return false;
                }
                if (a == ']' && stack.peek() == '[' || a == '}' && stack.peek() == '{' || a == ')' && stack.peek() == '(') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.empty();
    }

    // 逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int len = tokens.length;
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            if (!isOperation(str)) {
                int val = Integer.parseInt(str);
                stack.push(val);
            } else {
                int sum2 = stack.pop();
                int sum1 = stack.pop();
                switch (str) {
                    case "+":
                        stack.push(sum1 + sum2);
                        break;
                    case "-":
                        stack.push(sum1 - sum2);
                        break;
                    case "*":
                        stack.push(sum1 * sum2);
                        break;
                    case "/":
                        stack.push(sum1 / sum2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    public boolean isOperation(String str) {
        return str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/");
    }

}
